package algorithm.linkedlist;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
 * Difficulty : Medium
 *
 * 移除一个单链表，距离末尾第N个元素。（给定的N总是有效的）
 * 举栗：
 * Input : 1->2->3->4->5, and n=2
 * Output : 1->2->3->5
 *
 * @Author Antony
 * @Since 2018/7/9 17:40
 */
public class RemoveNthNodeFromEndOfList {

    public static void main(String[] args) {
        ListNode initNode = ListNode.initDate(1,7);
        System.out.println(removeNthEndNode(initNode,2).nodeString());
    }

    /**
     * (beats 98.62% - 9ms)
     * 尝试不创建dummy对象
     * 在代码里做了逻辑 preNode.next=first
     * 而且移动也是不同步的，preNode比head提前了一个节点，【所以此处移动是n次，不是n+1次】
     * 移动n次以后, 找到的就是倒数n节点的前一个节点
     */
    public static ListNode removeNthFromEnd_noObj(ListNode head, int n) {
        ListNode first = head;
        ListNode preNode = null;
        while(head != null){
            if(n<=0){
                preNode = preNode==null ? first : preNode.next;
            }
            head = head.next;
            n--;
        }
        if(preNode == null){
            // 说明要移除的是第一个元素，那么first指针就需要后移
            first = first.next;
        }else{
            preNode.next = preNode.next.next;
        }

        return first;
    }


    public static ListNode removeNthEndNode(ListNode head, int n){
        ListNode dummy = new ListNode(-1);
        ListNode first = head;
        dummy.next = first;
        while(head != null){
            if(n<=0){
                dummy = dummy.next;
            }
            head = head.next;
            n--;
        }

        // 还是要判断是否有节点移动
        if(dummy.val == -1){
            first = first.next;
        }else{
            dummy.next = dummy.next.next;
        }
        return first;
    }


    /**
     * (beats 97.96% - 11ms)
     * 思路：
     * 创建dummy对象, dummy.next = head
     * 然后nthPre指向dummy
     * dummy和nthPre一起移动，直到dummy为null，此时nthPre就是第n个节点的前一个节点
     *
     * 注意：
     * 条件的修改，
     * 因为是找n前面的节点，并且【dummyNode也是比head多一个节点的】，所以这里移动的步数是 【n=n+1】
     * 当n<=0的时候开始移动nthPre
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode nthPre = dummy;
        while(dummy != null){
            if(n<0){
                nthPre = nthPre.next;
            }
            dummy = dummy.next;
            n--;
        }
        nthPre.next = nthPre.next.next;
        return first.next;
    }
}
